package al239slideWindowMax;

import java.util.*;

public class Solution {

    // 暴力算法
    /*public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] temp= new int[nums.length-k+1];
        int max;
        for(int i=0;i<nums.length-k+1;i++){
            max = nums[i];
            for (int j=i+1;j<i+k;j++){
                if(max<nums[j]){
                    max = nums[j];
                }
            }
            temp[i] = max;
        }
        return temp;
    }*/

    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] temp= new int[nums.length-k+1];

        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {

            if(!queue.isEmpty() && queue.peekFirst()<i-k+1){
                queue.pollFirst();
            }
            while(!queue.isEmpty() && nums[queue.peekLast()] <nums[i]){
                queue.pollLast();
            }
            queue.offerLast(i);
            if(i >= k-1){
                temp[i-k+1]=nums[queue.peekFirst()];
            }
        }

        return temp;
    }



    public static void main(String[] args) {
        int[] sum ={1,3,-1,-3,5,3,6,7};
        int k=3;
        int[] i = maxSlidingWindow(sum, k);
        for (int j = 0; j < i.length; j++) {
            System.out.println(i[j]);
        }
    }
}
